package com.leetcode.problems042;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water/
 * @Date 2021/12/09 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    /**
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int res = 0;
        if(height.length <= 1){
            return res;
        }
        int left = 0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];

        while(left < right) {
            if (leftMax < height[right]) {
                if(leftMax > height[left + 1]){
                    res = res + leftMax - height[left + 1];
                }else{
                    leftMax = height[left + 1];
                }
                left = left + 1;
            }else{
                if(rightMax > height[right - 1]){
                    res = res + rightMax - height[right - 1];
                }else{
                    rightMax =  height[right - 1];
                }
                right = right - 1;
            }
        }

        return res;
    }


    public static void main(String[] args) {
        int[] candidates = {4,2,0,3,2,5};
        System.out.println(new Solution().trap(candidates));
    }
}
